class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        vector<int> diff;
        for (int i = 0; i < gas.size(); i++)
        {
            diff.push_back(gas[i] - cost[i]);
        }
        int end = 0;
        int sum = 0;
        for(int begin = 0; begin < gas.size(); begin++)
        {
            if(begin == end)
            {
                sum += diff[end];
                if(end == gas.size() - 1)
                    end = 0;
                else
                    end ++;
            }
            
            while(sum >= 0)
            {
                if(end == begin)
                    return begin;
                sum += diff[end];
                if(end == gas.size() - 1)
                    end = 0;
                else
                    end ++;
            }
            sum -= diff[begin];
        }
        return -1;
    }
};
